In order to define road geometry that may be utilized for mapping and navigational purposes, probe data may be collected from a variety of probe sources. For example, probe data that identifies the location and heading of a probe source at a particular moment in time may be provided by mobile telephones, such as smart phones, global positioning systems (GPS) that are carried by vehicles and other types of navigation systems. Several different techniques may be employed in order to create road geometry from probe data in instances in which the probe data has a relatively high density and includes relatively high frequency trajectory information.
For example, K-means trajectory clustering associates the trajectories of a cluster of seed points that are spatially close to one another and that have similar headings. However, K-means trajectory clustering generally requires probe data that has low noise and a high probe frequency which results in relatively short distances between probe points in order for the trajectory shape to approximate the road geometry. Another technique is trajectory merging in which probe trajectories are traversed and matching graph edges are merged. Trajectories that do not match existing edges create new edges in the graph. Trajectory merging also requires probe data having relatively low noise and high probe frequency such that there are relatively short distances between probe points in order for the trajectory shape to approximate the road geometry.
A kernel density estimation technique may also be utilized to create road geometry by computing an approximate kernel density estimate of trajectories of probe points or edges over an area of interest. The kernel density estimation technique applies a threshold to produce a binary image of the roads followed by the use of various methods, such as thinning, to produce road centerlines from the binary image. The kernel density estimation technique also requires high density probe data.
Another technique utilizes principal curves. Principal curves describe self-consistent curves that pass through the middle of point data. The principal curves technique may detect individual road segments that require additional logic to address intersections and to create a road network graph. The principal curves technique also requires high probe point density and uniform probe point density to produce the desired results.
As the foregoing techniques illustrate, current techniques for creating road geometry from probe data generally rely on high frequency trajectory information and high density probe data. In instances in which the probe data is sparse and/or noisy, such as in instances in which probe data is captured in a neighborhood in which traffic moves slowly and may be parked for hours at a time in a driveway or along a roadside, the foregoing techniques may be less successful in accurately generating the road geometry.
Further challenges are presented in instances in which bi-directional road geometry is to be created. A bi-directional road geometry representation is a representation of the road that describes the shape of the road, e.g., a by a curve or polyline, in each direction of travel regardless of whether a median is present. In this regard, bi-directional road geometry is desired in a number of instances including, for example, in conjunction with advanced driver assistance systems (ADAS) navigation functions as well as for geometry inclusion and/or change detection. As illustrated above, a number of existing techniques create the road geometry without reference to heading information, thereby limiting the creation of a bi-directional road geometry. Further, in addition to the challenges to road geometry creation caused by noisy probe data which exhibits positional and/or heading errors, the sparseness of probe data including the gaps and unevenness of probe data and overlapping probe data from adjacent roads increase the difficulty associated with the creation of accurate road geometry, particularly for bi-directional roads.